#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

class Solution
{
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        int l = 0, maxLen = 1;
        queue<pair<int, int>> q;
        for (int i = 1; i < n - 1; ++i)
        {
            q.push({i, i});
        }
        for (int i = 1; i < n; ++i)
        {
            if (s[i - 1] == s[i])
            {
                l = i - 1;
                maxLen = 2;
                if (i > 1 && i < n - 1)
                {
                    q.push({i - 1, i});
                }
            }
        }
        if (n < 3)
        {
            return s.substr(l, maxLen);
        }
        while (!q.empty())
        {
            auto [left, right] = q.front();
            q.pop();
            int cl = left - 1, cr = right + 1;
            if (s[cl] == s[cr])
            {
                l = cl;
                maxLen = cr - cl + 1;
                if (cl > 0 && cr < n - 1)
                {
                    q.push({cl, cr});
                }
            }
        }
        return s.substr(l, maxLen);
    }
};

// class Solution
// {
// public:
//     string longestPalindrome(string s)
//     {
//         // dp[i][j] i..j 回文
//         int n = s.size();
//         vector<vector<bool>> dp(n, vector<bool>(n, false));
//         int l = 0, maxLen = 1;
//         dp[0][0] = true;
//         for (int i = 1; i < n; ++i)
//         {
//             dp[i][i] = true;
//             if (s[i - 1] == s[i])
//             {
//                 dp[i - 1][i] = true;
//                 l = i - 1;
//                 maxLen = 2;
//             }
//         }
//         if (n < 3)
//         {
//             return s.substr(l, maxLen);
//         }
//         for (int len = 3; len <= n; ++len)
//         {
//             for(int i = 0; i <= n - len; ++i){
//                 dp[i][i+len-1] = dp[i+1][i+len-2] && (s[i] == s[i+len-1]);
//                 if(dp[i][i+len-1]){
//                     l = i;
//                     maxLen = len;
//                 }
//             }
//         }
//         return s.substr(l, maxLen);
//     }
// };

int main()
{

    // system("pause");
    return 0;
}
